package org.example;

import java.util.ArrayDeque;
import java.util.Deque;

public class Test1 {
    //leetcode 42 接雨水 https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150
    public int trap(int[] height) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(0);
        int ret = 0;
        for (int i = 1; i < height.length; i++) {
            while (!deque.isEmpty() && height[i] > height[deque.peekFirst()]) {
                if (deque.size() >= 2) {
                    int low = deque.removeFirst(), left = deque.peekFirst();
                    ret += (i-left-1)*(Math.min(height[i],height[left])-height[low]);
                }else {
                    deque.removeFirst();
                }
            }
            deque.addFirst(i);
        }
        return ret;
    }
}
